home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 13 - 1997 (partial) / 13.01 Jan 97 / Oddone.PreemptiveThreads Folder / FabWmemman.c next >
Encoding:
Text File  |  1997-01-03  |  5.6 KB  |  257 lines  |  [TEXT/CWIE]
  1. /*
  2. ANSI C _working_ equivalents for malloc, free, realloc, calloc;
  3. as a free bonus, you get ffcalloc() and fgetallocsize()
  4. unexplicably missing from the standard libraries.
  5.  
  6. malloc & free implementation based on Kernighan&Ritchie, 2nd ed.;
  7. realloc, calloc, ffcalloc, fgetallocsize by Fabrizio Oddone.
  8.  
  9. 2/1/95
  10. Modified the realloc routine in order to behave as described in
  11. section 7.10.3.4 of ANSI/ISO-C;
  12. that is:
  13. if ptr is a null pointer, realloc() allocates size bytes,
  14. else if size is 0, the memory block pointed to by ptr is freed.
  15. */
  16.  
  17.  
  18. //#include    <String.h>
  19. //#include    "UtilsSys7.h"
  20. #include    "FabWmemman.h"
  21.  
  22. //typedef long Align;
  23.  
  24. typedef union header Header;
  25.  
  26. union header {
  27.     struct {
  28.         Header *ptr;    // next block if on free list
  29.         size_t    size;        // size of this block (not bytes but MEMORY_UNITs)
  30.         } s;
  31. //    Align    x, y;
  32.     };
  33.  
  34. //#define    USETEMPORARYMEMORY    1
  35. //#define    USE64BITUNITS    1
  36.  
  37. #ifdef    USE64BITUNITS
  38. #define    MEMORY_UNIT    sizeof(Header)
  39. #else
  40. #define    MEMORY_UNIT    4    //sizeof(Header)
  41. #endif
  42.  
  43. /* NALLOC determines the amount of memory asked to the Mac OS */
  44. /* the allocated block is then handled by malloc */
  45. /* currently morecore asks "at least 64Kbytes" (you may want smaller blocks) */
  46.  
  47. #define    NALLOC    (2048UL / MEMORY_UNIT)    // minimum # units to request
  48.  
  49.  
  50. static Header base;    // empty list to get started
  51. static Header *freep = NULL;    // start of free list
  52.  
  53. static Header *morecore(size_t nu);
  54.  
  55. #define    HDR(p)    ((Header *)p)
  56.  
  57. void *fmalloc(size_t nbytes)
  58. {
  59. Ptr    p;
  60. Header *prevp;
  61. size_t    nunits, tempsize;
  62.  
  63. //DebugStr("\pNow entering fmalloc");
  64. nunits = (nbytes + sizeof(Header) - 1) / MEMORY_UNIT + 1;
  65. if ((prevp = freep) == NULL) {    // no free list yet
  66.     base.s.ptr = freep = prevp = &base;
  67.     base.s.size = 0;
  68.     }
  69.  
  70. for (p = (Ptr)prevp->s.ptr; ; prevp = HDR(p), p = (Ptr)HDR(p)->s.ptr) {
  71.     tempsize = HDR(p)->s.size;
  72.     if (tempsize >= nunits) {    // big enough
  73.         if (
  74. #ifdef    USE64BITUNITS
  75.         tempsize == nunits
  76. #else
  77.         tempsize <= nunits + 1
  78. #endif
  79.         )    // exactly
  80.             prevp->s.ptr = HDR(p)->s.ptr;
  81.         else {    // allocate tail end
  82.             HDR(p)->s.size -= nunits;
  83.             //p = (Header *)((Ptr)p + p->s.size * MEMORY_UNIT);
  84.             p += HDR(p)->s.size * MEMORY_UNIT;
  85.             HDR(p)->s.size = nunits;
  86.             }
  87.         freep = prevp;
  88.         return (p + sizeof(Header));
  89.         }
  90.     if (HDR(p) == freep)    // wrapped around free list
  91.         if ((p = (Ptr)morecore(nunits)) == NULL)
  92.             return NULL;    // none left
  93.     }
  94. }
  95.  
  96.  
  97. static Header *morecore(size_t nu)
  98. {
  99. Header *up;
  100.  
  101. if (nu < NALLOC)
  102.     nu = NALLOC;
  103. if (NULL == (up = (Header *)
  104. #ifdef USETEMPORARYMEMORY
  105.     NewHandleGeneral
  106. #else
  107.     NewPtr
  108. #endif
  109.         (nu * MEMORY_UNIT)))
  110.     return NULL;    // no space left
  111.  
  112. #ifdef USETEMPORARYMEMORY
  113. HLock((Handle)up);
  114. up = (Header *)*(Handle)up;
  115. #endif
  116. up->s.size = nu;
  117. ffree(up + 1);
  118. return freep;
  119. }
  120.  
  121. void ffree(void *bp)
  122. {
  123. Header *p, *tmp;
  124.  
  125. bp = HDR(bp) - 1;    // point to block header
  126. // !(bp > p && bp < p->s.ptr)
  127. //for (p = freep; bp <= p || bp >= p->s.ptr; p = p->s.ptr)
  128. //    if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
  129. //        break;    // freed block at start or end of arena
  130.  
  131. p = freep;
  132. tmp = p->s.ptr;
  133. while (bp <= p || bp >= tmp) {
  134.     if (p >= tmp && (bp > p || bp < tmp))
  135.         break;    // freed block at start or end of arena
  136.     p = p->s.ptr;
  137.     tmp = p->s.ptr;
  138.     }
  139.  
  140. if ((Ptr)bp + HDR(bp)->s.size * MEMORY_UNIT == (Ptr)tmp) {    // join to upper neighbor
  141.     HDR(bp)->s.size += tmp->s.size;
  142.     HDR(bp)->s.ptr = tmp->s.ptr;
  143.     }
  144. else
  145.     HDR(bp)->s.ptr = tmp;
  146. if ((Ptr)p + p->s.size * MEMORY_UNIT == (Ptr)bp) {    // join to lower neighbor
  147.     p->s.size += HDR(bp)->s.size;
  148.     p->s.ptr = HDR(bp)->s.ptr;
  149.     }
  150. else
  151.     p->s.ptr = bp;
  152. freep = p;
  153. }
  154.  
  155. /* reallocates and copies the old block only when necessary */
  156.  
  157. void *frealloc(void *ap, size_t s)
  158. {
  159. Ptr    bp;
  160. Header *p, *new_block;
  161. void *r = ap;
  162. size_t    cursize, nunits, temp;
  163.  
  164. if (ap) {
  165.     if (s) {
  166.         bp = (Ptr)ap - sizeof(Header);
  167.         nunits = (s + sizeof(Header) - 1) / MEMORY_UNIT + 1;
  168.         cursize = HDR(bp)->s.size;
  169.         if (nunits
  170.         #ifndef    USE64BITUNITS
  171.             + 1
  172.         #endif
  173.             < cursize) {
  174.         
  175.             HDR(bp)->s.size = nunits;
  176.             bp += nunits * MEMORY_UNIT;
  177.             HDR(bp)->s.size = cursize - nunits;
  178.             ffree(bp + sizeof(Header));
  179.             }
  180.         else if (nunits > cursize) {
  181.             for (p = freep; !(bp > (Ptr)p && bp < (Ptr)p->s.ptr); p = p->s.ptr)
  182.                 if (p >= p->s.ptr && (bp > (Ptr)p || bp < (Ptr)p->s.ptr))
  183.                     break;    // freed block at start or end of arena
  184.             temp = p->s.ptr->s.size + cursize;
  185.             if ((bp + cursize * MEMORY_UNIT == (Ptr)p->s.ptr) && (temp >= nunits)) {
  186.         // we can expand the block upwards in memory
  187.                 if (
  188.         #ifdef    USE64BITUNITS
  189.                 temp == nunits
  190.         #else
  191.                 temp <= nunits + 1
  192.         #endif
  193.                 ) {
  194.         // there is an adjacent free block matching exactly our needs
  195.                     HDR(bp)->s.size = temp;
  196.                     p->s.ptr = p->s.ptr->s.ptr;
  197.                     }
  198.                 else {
  199.         // we need to split the adjacent block
  200.                     new_block = (Header *) (bp + nunits * MEMORY_UNIT);
  201.                     new_block->s.ptr = p->s.ptr->s.ptr;
  202.                     new_block->s.size = temp - nunits;
  203.                     HDR(bp)->s.size = nunits;
  204.                     p->s.ptr = new_block;
  205.                     }
  206.                 freep = p;
  207.                 }
  208.             else {
  209.         // expanding not possible; reallocate, copy and free the old block
  210.                 if (r = fmalloc(s)) {
  211.                     BlockMoveData(ap, r, cursize * MEMORY_UNIT - sizeof(Header));
  212.                     ffree(ap);
  213.                     }
  214.                 }
  215.             }
  216.         }
  217.     else {
  218.         ffree(ap);
  219.         r = NULL;
  220.         }
  221.     }
  222. else
  223.     r = fmalloc(s);
  224.  
  225. return r;
  226. }
  227.  
  228. size_t fgetallocsize(const void *ap)
  229. {
  230. return ((Header *)ap - 1)->s.size * MEMORY_UNIT - sizeof(Header);
  231. }
  232.  
  233. void *fcalloc(size_t nelem, size_t nsize)
  234. {
  235. void *p;
  236. size_t    nbytes = nelem * nsize;
  237.  
  238. if (p = fmalloc(nbytes)) {
  239. // memset is poorly implemented, so we use a better one
  240. //    MyZeroBuffer(p, numOfLongs(nbytes + 3));
  241.     (void) memset(p, 0, nbytes);
  242.     }
  243. return p;
  244. }
  245.  
  246. void *ffcalloc(size_t s)
  247. {
  248. void *p;
  249.  
  250. if (p = fmalloc(s)) {
  251. // memset is poorly implemented, so we use a better one
  252. //    MyZeroBuffer(p, numOfLongs(s + 3));
  253.     (void) memset(p, 0, s);
  254.     }
  255. return p;
  256. }
  257.